<?php
/**
 * @title 785. 判断二分图 - 迭代
 * @author start2004
 */

class Solution {

    /**
     * @param Integer[][] $graph
     * @return Boolean
     */
    function isBipartite($graph) {
        /**
         * @since 2020-07-16 子集A,B
         */
        $hashA = [];
        $hashB = [];

        /**
         * @since 2020-07-17 查找子集的相邻点
         */
        $nextA = [];
        $nextB = [];

        /**
         * @since 2020-07-17 分子集
         */
        $a = true;
        while($graph){
            if($a){
                /**
                 * @since 2020-07-17 查找子集A的相邻点
                 */
                $nextB = self::find($nextA, $graph, $hashA, $hashB);
                if($nextB === false){
                    return false;
                    break;
                } else {}
            } else {
                /**
                 * @since 2020-07-17 查找子集B的相邻点
                 */
                $nextA = self::find($nextB, $graph, $hashB, $hashA);
                if($nextA === false){
                    return false;
                    break;
                } else {}
            }

            $a = !$a;
        }

        /**
         * @return
         */
        return true;
    }

    /**
     * @title 查找相邻点
     * @author start2004
     * @since 2020-07-17 Created
     *
     * @param array $nextA
     * @param array $graph
     * @param array $hashA
     * @param array $hashB
     * @return array|bool
     */
    function find($nextA = [], &$graph = [], &$hashA = [], &$hashB = []){
        /**
         * @since 2020-07-17 二分图由几个完全分离的图组成
         */
        if(empty($nextA)){
            /**
             * @since 2020-07-17 从graph取一个key作为A, 相邻点为B
             */
            $gKeys = array_keys($graph);
            $keyA = array_pop($gKeys);
            $nextA = [$keyA];
            $hashA[$keyA] = 1;
        } else {}

        /**
         * @since 2020-07-17 下次处理子集B的新元素
         */
        $nextB = [];

        /**
         * @since 2020-07-17 迭代处理子集A的新元素
         */
        foreach($nextA as $keyA){
            /**
             * @since 2020-07-16 不存在, 说明被另外一个子集B移除, 重复
             */
            if(!isset($graph[$keyA])){
                return false;
                break;
            } else {
                foreach ($graph[$keyA] as $gB){
                    /**
                     * @since 2020-07-16 当前B的相邻点都是子集B, 不能有子集A
                     */
                    if(isset($hashA[$gB])){
                        return false;
                        break;
                    } else {
                        /**
                         * @since 2020-07-16 新元素下次循环
                         */
                        if(!isset($hashB[$gB])){
                            $hashB[$gB] = 1;
                            $nextB[] = $gB;
                        }
                    }
                }
            }

            /**
             * @since 2020-07-16 处理完移除
             */
            unset($graph[$keyA]);
        }

        /**
         * @return
         */
        return $nextB;
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.16.php
 */
$datas = [
    [[1,3], [0,2], [1,3], [0,2]],
    [[1,2,3], [0,2], [0,1,3], [0,2]],
    [[1],[0,3],[3],[1,2]],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->isBipartite($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
